#include "headfiles.h"


static bool isASquare(int *s, int column_num, int row_index, int column_index, int size) {
    if (s == NULL ||
        column_num <= 0 ||
        column_index < 0 ||
        size < 1) {
        cout << "Invalid input argument" << endl;
        return false;
    }

    int i, j, index;
    // top and bottom
    for (j = 0; j < size; j++) {
        index = row_index * column_num + column_index + j;
        if (s[index] == 0) {
            return false;
        }

        index = (row_index + size - 1) * column_num + column_index + j;
        if (s[index] == 0) {
            return false;
        }
    }

    // left and right side
    for (i = 1; i < size - 1; i++) {
        index = (i + row_index) * column_num + column_index;
        if (s[index] == 0) {
            return false;
        }

        index = (i + row_index) * column_num + column_index + size - 1;
        if (s[index] == 0) {
            return false;
        }
    }

    return true;
}

bool calcColumnMaxSquare(int *s, 
                         int row_num, 
                         int column_num, 
                         int column_index, 
                         Segment *max_node) {
    int i, j;
    int size;
    bool ret;
    for (i = 0; i < row_num; i++) {
        size = ((row_num - i) > (column_num - column_index)) ?
                (row_num - i) : (column_num - column_index);
        while (size > max_node->size) {
            ret = isASquare(s, column_num, i, column_index, size);
            if (ret) {
                max_node->start = i;
                max_node->size = size;
            }
            size--;
        }
    }

    return true;
}

bool calcMaxSquare(int *s, 
                   int row_num, 
                   int column_num, 
                   int &max_x, 
                   int &max_y, 
                   int &size) {
    if (s == NULL ||
        row_num <= 0 ||
        column_num <= 0) {
        cout << "Invalid input argument!" << endl;
    }

    bool ret;
    Segment max_node;
    max_node.start = -1;
    max_node.size = 0;
    size = 0;

    for (int j = 0; j < column_num; j++) {
        calcColumnMaxSquare(s, row_num, column_num, j, &max_node);
        if (size < max_node.size) {
            size = max_node.size;
            max_x = max_node.start;
            max_y = j;
        }


        if (column_num - j < size) {
            break;
        }
    }

    return true;
}

